package cn.edu.njust.alg.leetcode;


public class Leetcode_79_word_search {

	/*
	 * 
	 * Given a 2D board and a word, find if the word exists in the grid.
	 * 
	 * The word can be constructed from letters of sequentially adjacent cell,
	 * where "adjacent" cells are those horizontally or vertically neighboring.
	 * The same letter cell may not be used more than once.
	 * 
	 * For example, Given board =
	 * 
	 * [ ["ABCE"], ["SFCS"], ["ADEE"] ] word = "ABCCED", -> returns true, word =
	 * "SEE", -> returns true, word = "ABCB", -> returns false.
	 */

	public static boolean exist(char[][] board, String word) {
		if (word == null || word.length() == 0
				|| word.length() > board[0].length * board.length) {
			return false;
		}
		boolean[][] visited = new boolean[board.length][board[0].length];
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if (board[i][j] == word.charAt(0)) {
					visited[i][j] = true;
					if (search(board, word.substring(1), i, j, visited)) {
						return true;
					} else {
						visited[i][j] = false;
					}
				}
			}
		}

		return false;
	}

	public static boolean search(char[][] board, String word, int i, int j,
			boolean[][] visted) {
		// System.out.println("i=" + i + " j=" + j + " " + word);
		if (word.length() == 0) {
			return true;
		}
		for (int m = -1; m < 2; m++) {
			for (int n = -1; n < 2; n++) {
				if ((m == 0 && n == 0) || m * n != 0 || i + m < 0 || j + n < 0
						|| i + m >= board.length || j + n >= board[i].length) {
					continue;
				}
				if (visted[i + m][j + n]) {
					continue;
				}
				if (board[i + m][j + n] == word.charAt(0)) {
					visted[i + m][j + n] = true;
					if (search(board, word.substring(1), i + m, j + n, visted)) {
						return true;
					} else {
						visted[i + m][j + n] = false;
					}
				}
			}
		}

		return false;
	}

	public static void main(String[] args) {
		char[][] board = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' },
				{ 'A', 'D', 'E', 'E' } };

		System.out.println(exist(board, "ABCE"));
		// String s = "1";
		// System.out.println(s.substring(1).length());
	}

}
